The present invention relates to geographic databases and more particularly, the present invention relates to an index that is useful for accessing and using data in geographic database.
Geographic data are used for various purposes in various different kinds of computing platforms. Geographic data are used in in-vehicle navigation systems to provide drivers of the vehicles with various useful navigation-related and map-related features. Geographic data are also used by navigation-related and map-related services on the Internet.
When using geographic data there is often a need to access the data spatially, i.e., to find data based on the locations of the geographic features represented thereby. One way to access geographic data spatially is to use a spatial index, such as a k-d-tree index. A k-d-tree index has a tree structure, having a root node, leaf nodes and intermediate nodes between the root node and the leaf nodes. Each node in a k-d-tree structure is part of a parent-child relationship. Each parent node includes control information from which one (of two or more) child nodes associated with the parent node can be distinguished based on a search key.
When a k-d-tree is used as a spatial index, the root node and intermediate nodes include two dimensional spatial boundary information (e.g., latitude and longitude) that relate to the indexed item of data. The indexed item of data can be an item of data that represents a single geographic feature. Alternatively, the indexed item of data can be a collection of data items that represent geographic features encompassed within a bounded area. As an example, a k-d-tree can be used as an index to collections (i.e., parcels) of data that represent geographic features located within separate rectangular areas. The nodes of a k-d-tree used for this purpose include the boundary information (i.e., maximum latitude, maximum longitude, minimum latitude, minimum longitude) that define the separate rectangular areas that contain the geographic features represented by the data in the respective parcels.
A k-d-tree used for organizing geographic data is described in U.S. Pat. No. 5,953,722, the entire disclosure of which is incorporated by reference herein.
When using geographic data, it is sometimes useful to access the data at different levels of detail (or granularity). Map display and route calculation are examples of two applications in which geographic data are sometimes used at different levels of detail. For example, when using geographic data with a map display application to display a map of an area, a greater level of detail is used for relatively larger scale maps and a lesser level of detail is used for relatively smaller scale maps. Similarly, when performing route calculation, it is often preferable not to consider smaller, low volume roads when determining a route between an origin and a destination.
In order to facilitate navigation functions that access and use geographic data at different levels of detail, data that represent geographic features are sometimes organized into layers based on a rank associated with the represented features. The lowest rank (e.g., 0) is associated with those features that are represented only when the finest level of detail is desired. In the case of roads, the lowest rank may be associated with side streets and alleys. On the other hand, the highest rank (e.g., 4) is associated with the most important features, i.e., those that would be displayed even at the coarsest level of detail. In the case of roads, the highest rank may be associated with expressways and major arterial roads.
When data representing geographic features are organized into layers, the lowest layer (e.g., 0) includes data representing geographic features of all ranks (e.g., 0-4). A highest layer (e.g., 4) includes data representing geographic features of only the highest rank (e.g., 4). Each other layer includes only those data that represent those geographic features of the associated rank and higher ranks. For example, layer 2 includes data that represent geographic features having ranks 2, 3 and 4. Layer 2 excludes data that represents geographic features of ranks 0 and 1. When data representing geographic features are organized into layers in this manner, a lowest layer has the greatest granularity and the highest layer has the least granularity.
These layers can exist as separate collections of the geographic data. When a navigation function requires the geographic data with a high level of detail, a lower layer is accessed and used. On the other hand, when a navigation function requires the geographic data with a low level of detail, a higher layer is accessed and used.
When data representing geographic features are organized into separate layers of granularity, a k-d-tree can be used to access the data spatially. A separate k-d-tree is used for each layer.
FIG. 1 shows a database structure 100 in which the data are organized into separate layers, labeled 0, 1, and 2. Each separate layer includes a separate collection of the geographic data, with layer 0 including the data that represent geographic features ranked 0, 1 and 2, layer 1 including the data that represent the geographic features ranked 1 and 2, and layer 2 including only the data that represent the geographic features ranked 2. Each separate layer also includes its own k-d-tree indexing information. Because each lower layer includes all the items of data represented in all higher layers, many items of data that represent the same feature are physically stored more than once. As an example, note that the item of data in the box labeled with an “x” appears in layer 0, layer 1 and layer 2.
An index for data can be implemented as either homogeneous or non-homogeneous. A homogeneous index appends the control information about related items of data to each indexed item of data. The k-d-tree structure in FIG. 1 is an example of an implementation of a homogeneous index. In the embodiment of FIG. 1, appended to each indexed item of data in the database 100 is the control information that indicates the related items of data. A homogeneous index provides advantages with relatively small data sets, e.g., those that fit entirely within a given computer's memory.
A non-homogeneous spatial index maintains the indexing data in a collection of small records that are separate from the indexed items of data. A non-homogeneous index is useful with relatively large data sets, i.e., those that exceed a given computer's memory. A non-homogeneous index has the benefits of being constructed and maintained separate from the indexed objects and of requiring relatively little space.
A homogeneous index and a non-homogeneous may be used together in a single database. A single database can include a non-homogeneous index maintained separate from the data being indexed and can also contain homogeneous index information appended to items of data.
A k-d-tree index (either homogeneous or non-homogeneous) used with a layered database works well for many applications. However, there is room for improvement. For example, it may be desired to provide more granularity, i.e., more layers or ranks of data. Further, it may be desired to make the indexing structure more flexible. Still further, it may be desired to index on additional properties of the data or the represented features.